In this article, we discuss the security of double-block-length (DBL) hash functions against the free-start collision attack. We focus on the DBL hash functions composed of compression functions of the form F(x) = (f(x), f(p(x))), where f is a smaller compression function and p is a permutation. We first show, in the random oracle model, that a significantly good upper bound can be obtained on the success probability of the free-start collision attack with sufficient conditions on p and the set of initial values. We also show that a similar upper bound can be obtained in the ideal cipher model if f is composed of a block cipher.

We first model the formal security model of multisignature scheme following that of group signature scheme. Second, we prove that the following three probabilistic multisignature schemes based on a trapdoor permutation have tight security; PFDH (probabilistic full domain hash) based multisignature scheme (PFDH-MSS), PSS (probabilistic signature scheme) based multisignature scheme (PSS-MSS), and short signature PSS based multisignature scheme (S-PSS-MSS). Third, we give an optimal proof (general result) for multisignature schemes, which derives the lower bound for the length of random salt. We also estimate the upper bound for the length in each scheme and derive the optimal length of a random salt. Two of the schemes are promising in terms of security tightness and optimal signature length. In appendix, we describe a multisignature scheme using the claw-free permutation and discuss its security.

Chen et al. introduced a new notion of a concurrent signature scheme for a fair exchange of signatures with two parties. Chen et al. also proposed a concrete scheme and proved its security under the assumption of discrete logarithm problem. Recently, Hiwatari and Tanaka extended the concept of concurrent signature to many-to-one setting. Hiwatari and Tanaka also proposed a concrete scheme; however, it requires some strong assumption to achieve the fair exchange and it is not efficient. This paper gives another construction of concurrent signature for many-to-one setting with multisignature scheme. Hereafter, we call it (n,1) concurrent signature scheme. The proposed scheme is more efficient than the scheme of Hiwatari and Tanaka in computation complexity and signature size, and achieves the fair exchange without the assumption required for the scheme of Hiwatari and Tanaka. This paper also gives a construction for the fair exchange of signatures in many-to-many setting, called (n,m) concurrent signature scheme, in appendix.

Although a great deal of research has been done on electronic cash schemes with blind multisignatures to prevent an insider attack, there is no discussion of a formal security model in the literature. Firstly we discussed the security model of e-cash schemes based on the blind multisignature scheme against a (restricted) attack model and proposed a concrete scheme proven to be secure in the model [1]; however, this attack model disallows an attacker from corrupting an issuing bank and shops in the forgery game. In this paper, first, we reconsider the security model to remove the restriction of the attack model. Second, we propose a new untraceable e-cash scheme with a blind multisignature scheme and prove that the proposed scheme is secure against the (non-restricted) attacks under the DDH assumption in the random oracle model.

We study on the security proof of the improved efficient-Rabin (ERabin) scheme and the F-FDHS scheme. First, we show that the security theorem of the improved ERabin scheme is not correct, and then provide a correct theorem for it. Second, we show that the security theorem of the F-FDHS scheme lacks an assumption. Finally, we present a way to modify the improved ERabin scheme and the F-FDHS scheme.

Ring signature scheme enables a signer to sign a message anonymously. In the ring signature scheme, the signer who wants to sign a document anonymously first chooses some public keys of entities (signers) and then generates a signature which ensures that one of the signer or entities signs the document. In some situations, however, the ring signature scheme allows the signer to shift the blame to victims because of the anonymity. The group signature scheme may be a solution for the problem; however, it needs an electronic big brother, called a group manager, who can violate the signer anonymity by himself, and a complicated key setting. This paper introduces a new notion of a signature scheme with signer anonymity, a deniable ring signature scheme (DRS), in which no group manager exists, and the signer should be involved in opening the signer anonymity. We also propose a concrete scheme proven to be secure under the assumption of the DDH (decision Diffie Hellman) problem in the random oracle model.

Multisignature schemes enable us to integrate multiple signatures into a single short signature. In 2001, Mitomi and Miyaji proposed a general model of multisignatures, in which signed messages are flexible and the signing order is verifiable and flexible. Several schemes that satisfy these properties have been proposed, but to the best of our knowledge, their verifiable orders are limited to only sequential structures unlike some order-verifiable (but not message-flexible) multisignatures. We define a signing structure as a labeled tree, which can represent any natural signing order including series-parallel graphs, and formalize a general model of multisignatures that makes good use of our structure. We present a security model for such signatures, give the construction based on the general aggregate signature developed by Boneh et al., and provide a security proof in the random oracle model.

The notion of correlation intractable function ensembles (CIFEs) was introduced in an attempt to capture the "unpredictability" property of random oracles [12]: If O is a random oracle then it is infeasible to find an input x such that the input-output pair (x,O(x)) has some desired property. In this paper, we observe relationships between zero-knowledge protocols and CIFEs. Specifically, we show that, in the non-uniform model, the existence of CIFEs implies that 3-round auxiliary-input zero-knowledge (AIZK) AM interactive proofs exist only for BPP languages. In the uniform model, we show that 3-round AIZK AM interactive proofs with perfect completeness exist only for easy-to-approximate languages. These conditional triviality results extend to constant-round AIZK AM interactive proofs assuming the existence of multi-input CIFEs, where "multi-input" means that the correlation intractability is satisfied with respect to multiple input-output pairs. Also, as a corollary, we show that any construction of uniform multi-input CIFEs from uniform one-way functions proves unconditionally that constant-round AIZK AM interactive proofs with perfect completeness only for easy-to-approximate languages.

We first model the variants of OAEP and SAEP by changing a construction and position of a redundancy, and establish a universal proof technique in the random oracle model, the comprehensive event dividing tree. We then make a taxonomical security consideration of the variants of OAEP and SAEP, based on the assumptions of one-wayness and partial-domain one-wayness of the encryption permutation, by applying the tree. Furthermore, we demonstrate the concrete attack procedures against all insecure schemes; we insist that the security proof failure leads to some attacks. From the security consideration, we find that one of the variants leads to a scheme without the redundancy; the scheme is not PA (plaintext aware) but IND-CCA2 secure. Finally, we conclude that some of them are practical in terms of security tightness and short bandwidth.

Up to present, proposed are many multi-signature schemes in which signers use respective moduli in the signature generation process. The FDH-based schemes are proposed by Mitomi et al. and Lysyanskaya et al.. The PSS-based schemes are proposed by Kawauchi et al. and Komano et al.. The FDH-based schemes have the advantage that the signature size is independent of the number of the signers. However, since the signature generation algorithm is deterministic, it has a bad reduction rate as a defect. Consequently, the signers must unfortunately use the keys large enough to keep the security. On the other hand, in the PSS-based schemes, good reduction rates can be obtained since the signature generation algorithms are probabilistic. However, the size of the random component shall overflow the security parameter, and thereby the signature size shall grow by the total size of the random components used the signers. That means, if the size of the random component is smaller, the growth of the signature size can be kept smaller. In this paper, we propose new probabilistic multi-signature scheme, which can be proven secure despite that smaller random components are used. We compare the proposed scheme and two existing schemes. Finally, we conclude that the proposed scheme is so-called optimal due to.

The complete subtree (CS) method is one of the most well-known broadcast encryptions which do not enforce the receivers to keep "online." This paper is to reduce the size of secret information which must be stored in a terminal of the method. In the original CS method, the size of the secret information increases as the number of terminals increases. It is shown in this paper that, by making use of a one-way trapdoor permutation, we can make the size constant regardless of the number of terminals. The security of the proposed scheme is investigated, and detailed comparison with other similar schemes is presented. The proposed scheme is suitable for practical implementations of the CS method.

We proposed a one-way trapdoor permutation f based multi-signature scheme which can keep tighter reduction rate. Assuming the underlying hash functions are ideal, our proposed scheme is not only provably secure, but are so in a tight. An ability to forge multi-signatures with a certain amount of computational resources implies the ability to invert a one-way trapdoor permutation f (on the same size modulus) with about the same computational effort. The proposed scheme provides the exact security against Adaptive-Chosen-Message-Attack and Adaptive-Insider-Attack by . can also attack in key generation phase, and act in collusion with corrupted signers.

In this paper, we propose a fast signature scheme which realizes short transmissions and minimal on-line computation. Our scheme requires a modular exponentiation as preprocessing (i.e., off-line computation). However, we need to acknowledge the existance of the following remarkable properties: neither multiplication nor modular reduction is used in the actual signature generation (i.e., on-line computation). Our scheme requires only two operations: hashing and addition. Although some fast signature schemes with small on-line computation have been proposed so far, those schemes require multiplication or modular reduction in the on-line phase. This leads to a large amount of work compared to that of addition. As far as we know, this is the first approach to obtain the fast signature without those two calculus methods.

Many oblivious transfer (OT) protocols have been proposed, however, most of them the security is assured in the random oracle model. Naor and Pinkas proposed 1-out-of-n OT which does not need random oracles. In this paper, we extend the 1-out-of-n OT to k-out-of-n OT protocol. Our protocol is efficient in the sense of both communication complexity and computation complexity.

In this paper we discuss how one can delegate his power to authenticate or sign documents to others who, again, can delegate the power to someone else. A practical cryptographic solution would be to issue a certificate that consists of one's signature. The final verifier checks verifies the chain of these certificates. This paper provides an efficient and provably secure scheme that is suitable for such a delegation chain. We prove the security of our scheme against an adaptive chosen message attack in the random oracle model. Though our primary application would be agent systems where some agents work on behalf of a user, some other applications and variants will be discussed as well. One of the variants enjoys a threshold feature whereby one can delegate his power to a group so that they have less chance to abuse their power. Another application is an identity-based signature scheme that provides faster verification capability and less communication complexity compared to those provided by existing certificate-based public key infrastructure.

This paper, for the first time, presents a provably secure signature scheme with message recovery based on the elliptic-curve discrete logarithm. The proposed scheme is proven to be secure in the strongest sense (i.e., existentially unforgeable against adaptively chosen message attacks) in the random oracle model under the discrete logarithm assumption. We give a concrete analysis of the security reduction. When practical hash functions are used in place of truly random functions, the proposed scheme is almost as efficient as the elliptic-curve version of the Schnorr signature scheme and existing schemes with message recovery such as the elliptic-curve version of the Nyberg-Rueppel and Miyaji schemes.

At Eurocrypt'98, Okamoto and Uchiyama presented a new trap-door (one-way) function based on factoring, while Fujisaki and Okamoto, at CRYPTO'99, showed a generic conversion from just one-way encryption to chosen-cipher secure encryption in the random oracle model. This paper shows that the result of combining both schemes is well harmonized (rather than an arbitrary combination) and, in the sense of exact security, boosts the level of security more than would be expected from [6]--The security of the scheme yielded by the combination is tightly reduced from factoring. This paper also gives a rigorous description of the new scheme, because this type of encryption may suffer serious damage if poorly implemented. The proposed scheme is at least as efficient as any other chosen-cipher secure asymmetric encryption scheme such as [2],[4],[13].

This paper presents a simple and generic conversion from a public-key encryption scheme that is indistinguishable against chosen-plaintext attacks into a public-key encryption scheme that is indistinguishable against adaptive chosen-ciphertext attacks in the random oracle model. The scheme obtained by the conversion is as efficient as the original encryption scheme and the security reduction is very tight in the exact security manner.

This paper proposes the first provably secure multi-signature schemes under the random oracle model. The security of our schemes can be proven in the sense of concrete security in Ref. [13]. The proposed schemes are efficient if the random oracle is replaced by practical hash functions. The essential techniques in our proof of security are the optimal reduction from breaking the corresponding identification to breaking signatures (ID Reduction Technique), and the hierarchical heavy row lemmas used in the concrete reduction from solving the primitive problem to breaking the identification scheme.